package com.michael.leetcode;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Optional;

@Slf4j
public class AnswerString_3403 {

    /**
     * 3403. 从盒子中找出字典序最大的字符串 I
     * 给你一个字符串 word 和一个整数 numFriends。
     * Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：
     * word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
     * 所有分割出的字符串都会被放入一个盒子中。
     * 在所有回合结束后，找出盒子中
     * 字典序最大的
     * 字符串。
     *
     * 示例 1：
     * 输入: word = "dbca", numFriends = 2
     * 输出: "dbc"
     * 解释:
     * 所有可能的分割方式为：
     * "d" 和 "bca"。
     * "db" 和 "ca"。
     * "dbc" 和 "a"。
     *
     * 示例 2：
     * 输入: word = "gggg", numFriends = 4
     * 输出: "g"
     * 解释:
     * 唯一可能的分割方式为："g", "g", "g", 和 "g"。
     *
     * 提示:
     * 1 <= word.length <= 5 * 103
     * word 仅由小写英文字母组成。
     * 1 <= numFriends <= word.length
     *
     */
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        int len = word.length();
        String re = "";
        for (int i = 0; i < len; i++) {
            String sub = word.substring(i, Math.min(i+ len-numFriends+1, len));
            if (sub.compareTo(re) > 0){
                re = sub;
            }
        }
        return re;
    }


    // 内存超了
    public String answerString1(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        Deque<String> deque = new ArrayDeque<>();
        int step = numFriends;
        while (step > 1) {
            int size = deque.size();
            if (size == 0) {
                split2(word, deque);
            } else {
                int t = 0;
                while (t < size) {
                    String s = deque.removeLast();
                    if (s.length() > 1) {
                        split2(s, deque);
                    } else {
                        if (!deque.contains(s)){
                            deque.offerFirst(s);
                        }
                    }
                    t++;
                }
            }
            step--;
        }
        String re = deque.pollFirst();
        while (!deque.isEmpty()) {
            String s = deque.pollLast();
            if (s.compareTo(re) > 0) {
                re = s;
            }
        }
        return re;
    }

    private void split2(String word, Deque<String> deque) {
        int len = 1;
        while (len < word.length()) {
            String l = word.substring(0, len);
            String e = word.substring(len, word.length());
            deque.offerFirst(l);
            deque.offerFirst(e);
            len++;
        }
    }

    @Test
    public void test() {
        String word = "dbca";
        int numFriends = 2;
        String s = answerString(word, numFriends);
        log.info("{}", s);
    }
}